package com.company.pddpre09;

import java.util.Scanner;

public class Main3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] goods = new int[N][2];
        for (int i = 0;i < N;i++){
            // 空间
            int C = sc.nextInt();
            // 收益
            int V = sc.nextInt();
            goods[i][0] = C;
            goods[i][1] = V;
        }
        int maxValue = getLargestValue(N,M,goods);
        System.out.println(maxValue);
    }

    private static int getLargestValue(int n, int m, int[][] goods) {
        int[][] dp = new int[n][m  + 1];
        for(int i = 0;i <= m;i++){
            // 放第0件物品
            if(goods[0][0] <= m){
                dp[0][i] = goods[0][1];
            }
        }

        for(int i = 1;i < n;i++){
            for(int j = 0;j <= m;j++){
                if(j >= goods[i][0]){
                    dp[i][j] = Math.max(dp[i - 1][j],goods[i][1] + dp[i - 1][j - goods[i][0]]);
                }
            }
        }

        return dp[n - 1][m];
    }
}
